#include <stdio.h>
#include <stdlib.h>

void countsort(int *arr,int n,int exp){
    int counts[10] = {0};
    // 计入counts
    for(int i=0;i<n;i++){
        counts[(arr[i]/exp)%10]++;
    }
    // 转化为 位置数组
    for(int i=1;i<10;i++){
        counts[i] += counts[i-1];
    }

    int *temp_arr = (int*)malloc(n * sizeof(int));
    // 倒序 稳定排序
    for(int i=n-1;i>-1;i--){
        int v = (arr[i]/exp)%10;
        temp_arr[counts[v]-1] = arr[i];
        counts[v]--;
    }
    
    for(int i=0;i<n;i++){
        arr[i] = temp_arr[i];
    }
    free(temp_arr);
}

void radixSort(int *arr, int n){
    // 找最大值
    int max = 0;  
    for(int i=0;i<n;i++){
        if(arr[i]>max){
            max = arr[i];
        }
    }
    //进行基数排序（计数排序按位数循环）
    for(int exp=1;exp<=max;exp*=10){
        countsort(arr,n,exp);
    }
}

int main(){
    int arr[] = {218,224,391,443,22,337,10000,1125,49,506};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    radixSort(arr,n);
    
    for(int i=0;i<n;i++){printf("%d ",arr[i]);}
    
    return 0;
}